In data communication, a network that connects a source node to a destination node may be said to include routers and links between the routers. Routers typically communicate, by way of the links, using a data communication protocol specific to the network, where different protocols are used to communicate for different purposes. A particular data communication protocol may be chosen for a network so as to optimize a particular parameter such as cost, delay or bandwidth. The Internet Protocol (IP) is one of the data communication protocols commonly used in networks. Other data communication protocols commonly used in networks include Asynchronous Transfer Mode (ATM), Synchronous Optical Network (SONET) and Synchronous Digital Hierarchy (SDH). Even within different protocol types (IP, Ethernet, ATM, SONET, etc.), there may be different service categories (for IP telephony, virtual private networks, etc.) with different Quality of Service (QoS) requirements (cost, delay, bandwidth, etc.).
In addition to data communication protocols, networks may make use of routing protocols and other technologies that allow the determination of a path for a Protocol Data Unit (PDU) to take through a network. One commonly used routing protocol is known as Open Shortest Path First (OSPF) and a technology for speeding up network traffic flow and making network traffic easier to manage is Multi-Protocol Label Switching (MPLS).
OSPF is an Internet routing protocol described in J. Moy, “OSPF Version 2”, Internet Engineering Task Force (IETF) Request for Comments (RFC) 2328, April 1998 and is classified as an Interior Gateway Protocol. This classification means that OSPF governs the distribution of routing information between routers in a given network. The OSPF protocol is based on link state information, where the state of a link may include cost, typical delay and available bandwidth. As such, OSPF is called a link state routing protocol. Each router in a given network using OSPF maintains an identical database describing the topology of the given network, i.e., which routers have links to which other routers and the state and qualities of those links. From resource information in the topology database, a routing table may be calculated. A routing table stores a “shortest” path from each node to each other node, which may not be shortest geographically, but may optimize one or more parameters.
Upon receiving a PDU, a router may examine the PDU to extract an address of a destination node. The router then consults the routing table to determine the next router in the shortest path to the destination node and transmits the PDU to the determined next router. In response to a topology change, e.g. a link failure, a router connected to the failed link originates a message called a Link State Advertisement (LSA) that is sent to all other routers in the given network. Each router, upon receiving a LSA, may then alter the topology database to reflect the advertised topological change and, subsequently, recalculate the local routing table based on the altered topology database. A router using the OSPF protocol may recalculate the local routing table quickly in the face of such topology changes, utilizing minimal routing protocol traffic.
MPLS is a technology for speeding up network traffic flow and increasing the ease with which network traffic flow is managed. A path between a given source node and a destination node may be predetermined at the source node. The routers along the predetermined path are then informed of the next router in the path through a message sent by the source node to each router in the predetermined path. Each router in the path associates a label with a mapping of output to the next router in the path. Accordingly, a router in an MPLS network may be called a Label Switched Router (LSR). By including, at the source node, the label in a label header associated with each PDU sent to the destination node, time is saved that would be otherwise needed for a router to determine the address of the next router to which to forward a PDU. The path arranged in this way is called a Label Switched Path (LSP). MPLS is called multiprotocol because it works with many protocols including IP, ATM and Frame Relay network protocols. An overview of MPLS is provided in R. Callon, et al, “A Framework for Multiprotocol Label Switching”, IETF Internet draft (work in progress), draft-ietf-mpls-framework-02.txt, November 1997, and a proposed architecture is provided in E. Rosen, et al, “Multiprotocol Label Switching Architecture”, IETF Internet draft (work in progress), draft-ietf-mpls-arch-02.txt, July 1998. (both documents are available at www.ietf.org)
In practice, a given LSR may receive a connection request, that is, a request that a path be built, from the given LSR to a specified destination LSR, for a stream of data to come. The given LSR determines a shortest path and sends a message to each LSR along the determined shortest path to build a virtual path for the stream of data. PDUs in the stream of data are associated with a label header that, when read by a LSR, assists the selection of the link to the next LSR in the virtual path.
In addition to moving traffic faster overall than IP, MPLS simplifies management of a network for QoS. Management of QoS relates to the aforementioned parameters of a link (cost, delay, bandwidth, etc.) or a path made up of several links. Before a source node may send a message informing routers, in a determined path through a network, of a label to associate with a next router, a negotiation may take place between the source node and each of the routers controlling links along the determined path. The negotiation may determine, for instance, whether the resources associated with each of the links along the determined path are sufficient to meet the QoS requirements of the stream of data for which the path is being set up.
Differentiated Services, or “Diff-Serv”, is described in Blake, S., et. al., “An Architecture for Differentiated Services”, IETF RFC 2475, December 1998, which may be found at www.ietf.org, and provides scalable and “better than best-effort” QoS. Routers that are aware of Diff-Sery are stateless and do not keep track of individual flows of traffic. As such, Diff-Sery is eligible for deployment in the Internet. A Diff-Sery Code Point (DSCP) is placed in a Differentiated Services (DS) field of the IP header of an IP packet to identify a Per Hop Behavior (PHB) to associate with the IP packet. PHB is typically used to specify queuing, scheduling and drop precedence. There are several defined PHBs including: (i) Best effort, (ii) Assured Forwarding (AF), and (iii) Expedited Forwarding (EF). At the ingress node in a Diff-Sery domain, a DSCP value is determined based on a classification of the incoming packet. At the interior nodes, the PHB is determined from the DSCP and appropriate QoS treatment is applied to the packet.
The MPLS label header has an experimental use field (EXP field) that has been proposed for use in providing support for Diff-Sery in MPLS. However, there are two basic problems for MPLS support of Diff-Serv. First, the DSCP is carried in a packet header, but the LSRs only examine the label header. Second, the DSCP has six bits but the EXP field has only three bits. There are two solutions defined in F. Le Faucheur et al., MPLS Support of Differentiated Services, IETF Internet Draft, draft-ietf-mpls-diff-ext-08.txt, February 2001, to remedy these two problems: (i) EXP-Inferred-PSC LSP (E-LSP), and (ii) Label-Only-Inferred-PSC LSP (L-LSP). PSC refers to a “PHB Scheduling Class”, which is a PHB group for which a common constraint is that ordering of at least those packets belonging to the same flow must be preserved.
For a E-LSP, an EXP-to-PHB mapping can be either preconfigured or explicitly signaled during the establishment of the E-LSP. An LSR receiving an incoming packet determines the PHB to be applied to the incoming packet by looking up the EXP field in the EXP-to-PHB mapping. For an L-LSP, an EXP-to-PHB mapping is a function of the PSC carried on the L-LSP, and is set up during the establishment of the L-LSP. Therefore, the PSC (i.e., used in queuing and scheduling) may already be known to the LSR based on the Label field. An LSR receiving an incoming packet determines the drop precedence, hence the PHB, to be applied to the incoming packet by looking up the EXP field in the EXP-to-PHB mapping.
Using the above protocols, or variants thereof, a source node in a network may dynamically provision resources within the network to establish or reconfigure a path through the network.
Traffic engineering (TE) is the process of selecting a path for routing a given connection (e.g., over an LSP) from a source node to a destination node such that the path satisfies constraints (bandwidth/administrative requirements) of the given connection, while simultaneously optimizing the network resource utilization and avoiding congestion. In classical TE, network traffic is distributed and link bandwidth is managed on an aggregate basis, that is, the TE information (e.g., unreserved link bandwidth) is advertised aggregately.
Diff-Sery aware TE (DS-TE) was designed on top of classical TE and with a goal being the maintenance of a relative proportion of different traffic on each link. For example, DS-TE limits the amount of guaranteed traffic below a given percentage of link capacity, while non-guaranteed service can be engineered or overbooked to offer an acceptable but lower level of service. On each DS-TE link, one Bandwidth Constraint (BC) value is configured for each class type. TE parameters (bandwidth constraint and unreserved link bandwidth) are advertised on a per class basis.
The term “Class Type” (CT) may be used to refer to a set of traffic trunks crossing a link, where the set is governed by a specific set of bandwidth constraints. A TE class is a pair including a class type and a preemption priority allowed for that CT. When ordinary TE is performed in a network, there is only one CT and one TE class per link (assuming a single pre-emption priority). When the DS-TE is performed, there can be up to eight class types, and up to eight TE-classes per link.
As defined in K. Kompella, Y. Rekhter, L. Berger, “Link bundling in MPLS traffic engineering”, IETF Internet draft, draft-ietf-mpls-bundle-04.txt, January 2003 (hereinafter “Kompella”), a TE bundled link is a logical entity that represents a group of physical and/or logical TE links connecting LSRs. The TE links making up a TE bundled link are called component links. As with ordinary TE links, TE parameters associated with a bundled TE link are advertised (e.g., via OSPF) to allow Constraint Based Routing. However, TE parameters for individual component links are not flooded. As such, an LSR that is not directly attached to a bundled link views that bundled link as a single link for path computation purposes.
As stated in Le Faucheur, et al, “Requirements for support of Diff-Serv-aware MPLS Traffic Engineering”, IETF Internet draft, draft-ietf-tewg-diff-te-reqts-07.txt, February 2003, and Le Faucheur, et al, “Protocol extensions for support of Diff-Serv-aware MPLS Traffic Engineering”, IETF Internet draft, draft-ietf-tewg-diff-te-proto-04.txt, June 2003, DS-TE provides the capability to engineer network traffic on a per “class” basis instead of on an aggregate basis. With DS-TE, admission control may be performed on a per class basis rather than on an aggregate basis, as with classical TE. Consequently, DS-TE requires that certain TE parameters are advertised on a per class basis. The hereinbefore-referenced draft-ietf-tewg-diff-te-proto-04.txt specifies how those TE parameters are advertised on a per class basis on non-bundled links. Kompella specifies how to derive TE parameters for a bundled link from those of its component links.
S. Sivabalan, F. Le Faucheur, R. Zhang, “Link Bundling support for Diff-Sery aware Traffic Engineering”, Internet draft, June 2003, (hereinafter “Sivabalan”) captures the relevant enhancements to Kompella so that the necessary TE parameters are advertised on a per-class basis for a TE bundled link. This allows DS-TE to be supported over bundled links.
Link bundling may be employed to improve routing scalability by reducing the amount of information handled by whichever link state advertising protocol is being used, such as the OSI Intermediate System-to-Intermediate System (IS-IS) and the IETF OSPF routing protocols, and their recent traffic engineering versions IS-IS-TE and OSPF-TE.
The benefits of link bundling include inadvertent load sharing among the component links as well as redundancy in the event that one or more of the component links in the bundled link fail. Additionally, link bundling allows incremental increases in capacity at finer granularity (e.g., allowing for a 6 Mbps “trunk” using four T1 links). The link bundling aspect of Ethernet LAG (Link Aggregation) is also receiving a strong industry interest for increasing capacity and survivability.
TE techniques and protocols can implement a variety of Bandwidth Constraint (BC) models, which control resource partitioning and sharing among the multiple class types (Bandwidth Pools) sharing the link. Examples of the BC models include the Maximum Allocation model and the Russian Doll Model.
Kompella and Sivabalan specify how to derive TE parameters for a given bundled link from the TE parameters of the component links of the given bundled link for network environments where the classical DS or DS-TE is performed, respectively. However, neither Kompella nor Sivabalan specify how to select a component link for accommodating a new connection request when more than one component link has enough unreserved bandwidth at the connection admission time. Although it is well known that load balancing is very important for improving QoS and achieving bandwidth usage efficiency, no load balancing scheme has yet been specified, and it has been left for the vendors to design an appropriate load balancing scheme. Similarly, neither Kompella nor Sivabalan specify how to recover connections upon the failure of one or multiple component links, and how to re-balance the traffic after the recovery from a component link failure.
Many vendors are known to use proprietary hashing algorithms to perform load balancing. These hashing algorithms distribute incoming PDUs based on MAC address, IP address, port number, etc. However, different QoS requirements were not considered. Such techniques are suitable for connectionless traffic, where no bandwidth reservation is possible.
Some load balancing techniques have been implemented for Private Network-Network Interface (P-NNI) ATM networks. However, these techniques are somewhat limited in the methods they use, and may be shown not to lend themselves well to the MPLS-TE protocols and standards.
As well, Inverse Mux in ATM (IMA) uses bundled links in a different way than MPLS. In IMA, the cells from each connection are distributed evenly across all available links using hardware assist mechanisms. All component links share the load equally, and there is no visibility or variability of BW utilization for the component links.
Clearly, an improvement is required in traffic engineering and bandwidth management of bundled links. Of particular interest would be methods that lend themselves well to the MPLS-TE protocols and standards.